package me.mingshan.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
 *
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 *
 * @author hanjuntao
 * @date 2025/7/2 0002
 */
public class L_215_kth_largest_element_in_an_array {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 3, 1};

        // 123564
        // left = 2
        // 6-2 = 4

        //System.out.println(findKthLargest2(nums, 2));

        System.out.println(findKthLargest3(nums, 3));
    }

    /**
     * 暴力解法:
     *
     * 1. 对数组进行排序
     * 2. 获取数组倒数第 k 个元素
     *
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i == nums.length - k) {
                return nums[i];
            }
        }
        return 0;
    }

    /**
     * 堆排序
     *
     * 可以使用最小堆（优先队列）来解决这个问题。将数组中的元素依次加入最小堆中，当堆的大小超过K时，
     * 就弹出堆顶元素（即当前最小的元素）。最后，堆顶元素即为第K个最大的元素。
     *
     * 时间复杂度：O(nlogk)
     * 空间复杂度：O(k)
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest2(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // 小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < nums.length; i++) {
            // 添加元素
            pq.offer(nums[i]);

            // 保持堆的大小小于等于 k
            // 如果大于k，就弹出堆顶元素
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // 获取堆顶元素
        return pq.peek();
    }

    /**
     * 快排
     *
     * 1. 随机选择一个元素作为 pivot
     * 2. 将数组分为小于 pivot 的元素和等于 pivot 的元素
     * 3. 递归处理小于 pivot 的元素和等于 pivot 的元素
     *
     * 右边都是比 pivot 大的元素，左边都是小于 pivot 的元素
     *
     *
     *
     * 时间复杂度：O(n)
     * 空间复杂度：O(logn)
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest3(int[] nums, int k) {
        return findKthLargest3inner(nums, k, 0, nums.length - 1);
    }

    private static int findKthLargest3inner(int[] nums, int k, int i, int j) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        if (i > j) {
            return -1;
        }

        int pivot = nums[i];
        int left = i;
        int right = j;

        while (left < right) {
            // right 先从后往前走
            // 找到第一个比 pivot 小的元素
            while (left < right && nums[right] >= pivot) {
                right--;
            }

            // left 从前往后走
            // 找到第一个比 pivot 大的元素
            while (left < right && nums[left] <= pivot) {
                left++;
            }

            // 交换 left 和 right的值
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }

        // left 和 right 相等，交换 left 和 pivot
        if (left == right && nums[left] < pivot) {
            int temp = nums[left];
            nums[left] = pivot;
            nums[i] = temp;
        }

        // 判断当前left 是多少大的元素
        int leftW = nums.length - left;

        // 如果刚好相当于 k，返回 pivot
        if (leftW == k) {
            return nums[left];
        }

        // 如果当前left的是第几大的位置比k大，比如left 是第4大，k是第2大，需要找left右边的
        // 说明第 k 个最大的元素在 left 右边
        if (leftW > k) {
            return findKthLargest3inner(nums, k, left + 1, j);
        }

        // 如果当前left的是第几大的位置比k小，说明第 k 个最大的元素在 left 左边
        if (leftW < k) {
            return findKthLargest3inner(nums, k, i, left - 1);
        }

        return -1;
    }
}
